package DataStructure.priority;


public class MinPriorityQueue<T extends Comparable<T>> {
    private T[] imtes;
    private int N;

    public MinPriorityQueue(int capacity){
        this.imtes=(T[])new Comparable[capacity+1];
        this.N=0;
    }

    private boolean less(int i,int j){
        return imtes[i].compareTo(imtes[j])<0;
    }

    private void exch(int i,int j){
        T temp=imtes[i];
        imtes[i]=imtes[j];
        imtes[j]=temp;
    }



    public int size(){
        return N;
    }

    public boolean isEmpty(){
        return N==0;
    }



    public void insert(T t){
        imtes[++N]=t;
        swim(N);
    }

    //删除最小值并返回
    public T delMin(){
        T min=imtes[1];
        exch(1,N);
        N--;
        sink(1);
        return min;
    }

    private void swim(int k){
        while (k>1){
            if(less(k,k/2)){
                exch(k,k/2);
            }
            k=k/2;
        }
    }

    private void sink(int k){
        while (2*k<=N){
            int min;
            if(2*k+1<=N){
                if(less(2*k,2*k+1)){
                    min=2*k;
                }else {
                    min=2*k+1;
                }
            }else {
                min=2*k;
            }
            if(less(k,min)){
                break;
            }
            exch(k,min);
            k=min;
        }
    }
}
